package slidingWindow;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 * 限制：
 * 1 <= s.length, t.length <= 105
 * s 和 t 由英文字母组成
 */

public class MinWindowSubStr_76 {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }

        // 记录目标字符串各字符的数量，遍历t可得
        Map<Character, Integer> target = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            if (target.containsKey(t.charAt(i))) {
                target.put(t.charAt(i), target.get(t.charAt(i))+1);
            } else {
                target.put(t.charAt(i), 1);
            }
        }

        // 记录当前窗口符合条件的字符的数量，并不是所有字符的数量
        Map<Character, Integer> window = new HashMap<>();
        // 记录满足数量要求的字符个数
        int valid = 0;
        // 定义滑动窗口的2个指针，都向右遍历，
        // 先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）
        // 再停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求，同时，每次增加 left，都要更新一轮最小子串。
        // 重复，直至right到达尽头
        int left = 0;
        int right = 0;
        int len = Integer.MAX_VALUE;
        int start = 0;
        while (right < s.length()) {
            // c是将移入窗口的字符
            char c = s.charAt(right);
            right++;
            if (target.containsKey(c)) {
                if (window.containsKey(c)) {
                    window.put(c, window.get(c)+1);
                } else {
                    window.put(c, 1);
                }

                if (window.get(c).equals(target.get(c))) {
                    valid++;
                }
            }

            // 右侧窗口一直移动直至当前窗口包含target的全部字符，再判断左侧窗口是否要收缩
            while (valid == target.size()) {
                // 在这里覆盖最小子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是即将移出窗口的字符
                char d = s.charAt(left);
                left++;
                if (target.containsKey(d)) {
                    // 如果目标字符串中包含该字符，让valid--
                    if (target.get(d).equals(window.get(d))) {
                        valid--;
                    }
                    // 有字符移出，window[d]--
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        if (len == Integer.MAX_VALUE) {
            return "";
        } else {
            return s.substring(start, start + len);
        }
    }
}
